package com.scqzy.shengchunqiang.sword2offer.day15;

import com.scqzy.shengchunqiang.structure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @Description: 剑指 Offer 34. 二叉树中和为某一值的路径
 * @Author 盛春强
 * @Date 2021/8/22 23:19
 */
public class PathSum {
    List<List<Integer>> paths = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        getPath(new ArrayList<>(), root, target);
        return paths;
    }

    private void getPath(List<Integer> path, TreeNode node, int target) {
        if (Objects.nonNull(node)) {
            path.add(node.val);
            if (target - node.val == 0 && Objects.isNull(node.left) && Objects.isNull(node.right)) {
                paths.add(new ArrayList<>(path));
            } else {
                getPath(path, node.left, target - node.val);
                getPath(path, node.right, target - node.val);
            }
            path.remove(path.size() - 1);
        }
    }
}
